1. Field of the Invention
The present invention relates to a motion vector detecting apparatus and a method for detecting a motion vector used in a motion picture compression encoder or the like.
2. Description of the Related Art
A motion detection scheme of block-matching type, where matching areas are searched from two different images in connection with a moving object to thus detect a motion vector of the matching areas, is a technique important for monitoring a general image or the like. This scheme has recently come into use as a basic technique, particularly for a moving picture compression encoding technique, such as MPEG for highly-efficiently encoding a moving picture. Detection of a motion vector involves processing entailing an enormous amount of computation, and many techniques have hither to been developed with a view toward rendering computation faster and more efficient (see, e.g., JP-A-1-295379).
A motion vector sensor having correlation computation means such as that shown in a block diagram shown in FIG. 1 has hitherto been available. A motion vector of a noteworthy area (hereinafter called an “input block”) of an input image is detected through use of a preceding frame (hereinafter called a “reference image”) retained by reference image memory 102 and a current frame (hereinafter called an “input image”) retained by input image memory 101. In this case, as illustrated in a conceptual drawing of a search range shown in FIG. 2, a correlator 103 determines a correlation coefficient of the input block and a correlation coefficient of another image area (hereinafter called a “reference block”) which is identical in size with the input block and which is located in a position vertically or horizontally distant from the input block, with a location in the reference image corresponding to the location of the input block being taken as a reference position for starting a search. The thus-determined correlation coefficients are stored in correlation coefficient memory 104.
The correlation coefficients of the respective input blocks are compared with each other by a comparator 105. Search standard positions are shifted to a location where maximum correlation is achieved (i.e., the minimum correlation coefficient is achieved). Thus, a location where the correlation of the search standard positions becomes maximum is searched while reference blocks in a direction where correlation coefficients are not yet computed are being subjected to correlation operation.
FIG. 3 is a view for describing the method by means of a specific example, and the method is called a one-at-a-time method. By reference to FIG. 3, a related one-at-a-time method is described. First, a correlation coefficient of a search position 1 where search is started is computed. Next, a correlation coefficient of a right search position 2 and that of a left search position 3 are computed in a time-series fashion, and a comparator finds a minimum value from among the correlation coefficients of the search positions 1 to 3. Here, on the assumption that the correlation coefficient of the search position 3 is smaller than those of the other search positions, the correlation coefficient of a position (a search position 4) to the left of the search position 3 is computed, and the comparator determines whether the correlation coefficient of the search position 3 is larger or smaller than that of the search position 4. the result of comparison is assumed to be (the correlation coefficient of the search position 4)<(the correlation coefficient of the search position 3).
In a case where the correlation coefficients have been computed in the same manner up to the correlation coefficient of a search position 7, when there is obtained a relationship of (a correlation coefficient of a search position 6)<(the correlation coefficient of the search position 7) (i.e., the correlation coefficients of the right and left search positions are larger than the correlation coefficient of the center search position), the correlator 103 determines a correlation coefficient of an upper search position 8 and a correlation coefficient of a lower search position 9 with reference to the search position 6 in a time-series fashion. The comparator 104 determines the minimum correlation value from the correlation coefficients of the search positions 6, 8, and 9. Provided that the correlation coefficient of the search position 8 is presumed to be minimum, a correlation coefficient of a right search position 10 and that of a left search position 11 with reference to the search position 8 are computed, and the comparator 103 determines the minimum value among the thus-computed correlation coefficients.
Subsequently, the correlation coefficient of the right search position and that of the left search position are determined in the same manner. The search position having a higher degree of correlation (i.e., a smaller correlation coefficient) is taken as the center of search. When the correlation coefficient of the center search position is the largest when compared with that of the right search position and that of the left search position, a correlation coefficient of an upper search position and that of a lower search position are searched, whereby the reference is changed to a position having a higher degree of correlation. Search of a position where the correlation of the center with respect to those of the upper, lower, right, and left search positions becomes maximum is finally pursued, thereby detecting as a motion vector the search position which exhibits the maximum correlation. As mentioned above, according to the related method, computation of the correlation coefficients of adjacent search positions and determination of the position exhibiting the maximum correlation are performed through consecutive processing.
A common correlation operation method is for subjecting to addition an absolute value of a difference between the reference image and the input image. A formula for computing a correlation coefficient is shown in Equation 1.
                              S          =                                    ∑                              x                =                0                            Nx                        ⁢                                          ∑                                  y                  =                  0                                Ny                            ⁢                                                                                    I                    ⁡                                          (                                                                        Px                          +                          x                                                ,                                                  Py                          +                          y                                                                    )                                                        -                                      R                    ⁡                                          (                                                                        Px                          +                          x                          +                          dx                                                ,                                                  Py                          +                          y                          +                          dx                                                                    )                                                                                                                          ⁢                                  ⁢                  Nx          ,                      Ny            ⁢                                                  ⁢            …            ⁢                                                  ⁢            lateral            ⁢                                                  ⁢            and            ⁢                                                  ⁢            longitudinal            ⁢                                                  ⁢            size            ⁢                                                  ⁢            of            ⁢                                                  ⁢            a            ⁢                                                  ⁢            block                          ⁢                                  ⁢                              I            ⁡                          (                              x                ,                y                            )                                ,                                    R              ⁡                              (                                  x                  ,                  y                                )                                      ⁢                                                  ⁢            …            ⁢                                                  ⁢            image            ⁢                                                  ⁢            data            ⁢                                                  ⁢            pertaining            ⁢                                                  ⁢            to            ⁢                                                  ⁢            the            ⁢                                                  ⁢                          position              ⁢                                                          (                              x                ,                y                            )                        ⁢                                                  ⁢            of            ⁢                                                  ⁢            an            ⁢                                                  ⁢            input            ⁢                                                  ⁢            image                          ⁢                                  ⁢                  Px          ,                      Py            ⁢                                                  ⁢            …            ⁢                                                  ⁢            reference            ⁢                                                  ⁢            retrieval            ⁢                                                  ⁢            positions                          ⁢                                  ⁢                  dx          ,                      dy            ⁢                                                  ⁢            …            ⁢                                                  ⁢            the            ⁢                                                  ⁢            amount            ⁢                                                  ⁢            of            ⁢                                                  ⁢            deviation            ⁢                                                  ⁢            from            ⁢                                                  ⁢            the            ⁢                                                  ⁢            retrieval                          ⁢                                  ⁢                                  ⁢                  reference          ⁢                                          ⁢          positions                                    [                  Equation          ⁢                                          ⁢          1                ]            
As indicated by the above formula, the correlating operation requires a lot of computing operations. Therefore, as shown in FIG. 4, there has generally been performed a processing method for dividing blocks into a group of blocks located in even-numbered positions and a group of blocks located in odd-numbered positions in advance to thus sample image data (hereinafter called “sub-sampling”), thereby diminishing the number of computing operations required to perform correlating operation.
Under the above-described related-art method, only one correlating operator is provided. Therefore, there exists a problem of search of the maximum correlation position involving consumption of an extremely long time. For instance, in the embodiment shown in FIG. 3, performance of fifteen correlating operations is required.
Computation of a correlation coefficient usually entails consumption of much time. Therefore, under a method for shortening the time by sub-sampling the image data pertaining to the standard blocks and the image data pertaining to the reference blocks, the sub-sampled image data pertaining to the reference blocks in the even-numbered positions differ from the sub-sampled image data pertaining to the reference blocks in the odd-numbered positions as shown in FIG. 4.
For instance, in FIG. 4, the sub-sampled image data required to compute blocks of the first row differ from the sub-sampled image data required to compute blocks of the second row. Eventually, pipeline processing becomes impossible to perform, because of the sub-sampling operations. When compared with a case where computing operation is performed through pipeline processing, there arises a problem of the correlating operation requiring a much longer time.